package main

import (
	"fmt"
	"math"
	"sort"
	"strconv"
	"strings"
	"sync"
	"unicode"
)

var (
	counter int
	mutex   sync.Mutex
)

func increment() {
	//mutex.Lock()
	counter++
	//mutex.Unlock()
}
func main() {
	s := "hello world"
	whatAmi := func(i interface{}) {
		switch t := i.(type) {
		case byte:
			fmt.Println("是byte", t)
		case rune:
			fmt.Println("是rune", t)
		default:
			fmt.Println("都不是")
		}
	}
	//for i:=0; i<len(s); i++ {
	//	whatAmi(s[i])
	//}

	for _,v := range s {
		whatAmi(v)
	}

}

// 提供一个值, 每次调用函数会指定对值进行累加
func Accumulate(value int) func() int {
	// 返回一个闭包
	return func() int {
		// 累加
		value++
		// 返回一个累加值
		return value
	}
}

// 实际打印的函数
func rawPrint(rawList ...interface{}) {
	// 遍历可变参数切片
	for _, a := range rawList {
		// 打印参数
		fmt.Println(a)
	}
}

// 打印函数封装
func print(slist ...interface{}) {
	// 将slist可变参数切片完整传递给下一个函数
	//rawPrint(slist...)
	rawPrint("fmt", slist)

}

var str string
var str4 = ""

//测试面试题
func test1() {
	grumpy := []int{0, 0, 1, 1}
	customers := []int{2, 6, 6, 9}
	for k, v := range grumpy {
		if v == 0 {
			customers[k] = 0
		}
		grumpy[k] = -1
	}
	fmt.Println(customers)

}

// 测试标准输入和输出
func testIo() {
	//var a,b int
	//fmt.Scan(&a,&b)
	//fmt.Printf("(a+b): %v\n", (a+b))
	//
	//var c, d int
	//fmt.Scanln(&a, &b) // 1 2
	//fmt.Printf("(a + b): %v\n", (c + d)) // 3
	//
	//reader := bufio.NewReader(os.Stdin)
	//str, _ := reader.ReadString('\n')
	//str = strings.TrimSpace(str) // 去除首尾空格或换行符
	//fmt.Println(str)

	// scanner := bufio.NewScanner(os.Stdin)
	// scanner.Scan()
	// input := scanner.Text()
	// fmt.Printf("input:%v\n", input)
}

func testString() {
	str := "死神来了， 死神bye bye"
	comma := strings.Index(str, "，")
	pos := strings.Index(str[comma:], "死神")
	fmt.Println(comma, pos, str[comma+pos:])

}

func hj4() {
	var input string
	fmt.Scan(&input)
	length := len(input)

	if length <= 8 {
		for i := length; i < 8; i++ {
			input += "0"
		}
		fmt.Println(input)
	} else {
		for i := 1; i <= length; i++ {
			if i%8 == 0 {
				str := input[i-8 : i]
				fmt.Println(str)
			}
		}
		num := length % 8
		if num != 0 {
			lastStr := input[length-num : length]
			for i := num; i < 8; i++ {
				lastStr += "0"
			}
			fmt.Println(lastStr)
		}

	}

}

func hj9() {
	var str string
	// var inputMap map[int32]bool
	inputMap := make(map[int32]bool)
	fmt.Scan(&str)
	for _, v := range str {
		v -= 48
		inputMap[v] = true

	}

	for i := len(str) - 1; i >= 0; i-- {
		v := int32(str[i]) - 48
		if inputMap[v] {
			inputMap[v] = false
			fmt.Printf("%d ", v)
		}
	}

}

// 明明的随机数
func hj3() {
	var n int
	fmt.Scan(&n)
	var arr []int
	// arr := [...]int{}
	aMap := make(map[int]bool)
	for i := 0; i < n; i++ {
		var num int
		fmt.Scan(&num)
		aMap[num] = true
	}

	for index, v := range aMap {
		if v {
			arr = append(arr, index)
		}
	}

	sort.Slice(arr, func(i, j int) bool { return arr[i] < arr[j] })

	for _, v := range arr {
		// fmt.Printf("%d", v)
		fmt.Println(v)
	}

}

func code58Bob(s string) int {
	strArr := strings.Split(s, " ")

	lastWordIndex := len(strArr) - 1
	var length int = len(strArr[lastWordIndex])
	fmt.Printf("%d\n", length)
	return length
}

// 参考的题解
func code58(s string) (ans int) {
	index := len(s) - 1
	for s[index] == ' ' {
		index--
	}
	for index >= 0 && s[index] != ' ' {
		ans++
		index--
	}
	return
}

func lastWordLen(str string) (length int) {

	for i := len(str) - 1; i >= 0; i-- {
		if str[i] != ' ' {
			length += 1
		} else {
			break
		}
	}
	return
}

// 1684. 统计一致字符串的数目
func code1684(allowd string, words []string) int {

	chars := make([]bool, 26)

	for _, v := range allowd {
		temp := v - 'a'
		fmt.Println(temp)
		chars[v-'a'] = true
	}

	nums := 0
OUT:
	for _, word := range words {
		for _, char := range word {

			if !chars[char-'a'] == true {
				continue OUT
			}
		}
		nums++

	}

	return nums
}

// 67. 二进制求和
func code67(a string, b string) string {
	ans := ""
	carry := 0
	lenA, lenB := len(a), len(b)
	n := max(lenA, lenB)

	for i := 0; i < n; i++ {
		if i < lenA {
			carry += int(a[lenA-i-1] - '0')
		}

		if i < lenB {
			carry += int(b[lenB-i-1] - '0')
		}
		//strconv.Itoa函数的参数是一个整型数字，它可以将数字转换成对应的字符串类型的数字。
		ans = strconv.Itoa(carry%2) + ans
		carry /= 2
	}

	if carry > 0 {
		ans = "1" + ans
	}

	return ans

}

func max(x int, y int) int {
	if x > y {
		return x
	}
	return y
}

func code125Bob(s string) bool {
	res := []rune(s)
	fmt.Println(res)

	arr := make([]rune, len(s)-1)
	stringToRuneArr(s, arr)
	//1.所有大写转为小写

	return true
	// 2.移除所有非字母数字字符
	// 3.空字符串也是回文

}

func code125(s string) bool {
	var sgood string
	for i := 0; i < len(s); i++ {
		if checkChar(s[i]) {
			sgood += string(s[i])
		}
	}
	sgood = strings.ToLower(sgood)

	n := len(sgood)

	for i := 0; i < n/2; i++ {
		if sgood[i] != sgood[n-i-1] {
			return false
		}

	}

	return true

}

func checkChar(char byte) bool {
	return char >= 'A' && char <= 'Z' || char >= 'a' && char <= 'z' || char >= '0' && char <= '9'
}

func stringToRuneArr(s string, arr []rune) {
	src := []rune(s)
	for i, v := range src {
		if i >= len(arr) {
			break
		}
		arr[i] = v
	}
}

func code168(columnNumber int) string {
	var str string
	for {
		columnNumber--
		if columnNumber < 0 {
			break
		}
		char := string(columnNumber%26 + 'A')
		columnNumber /= 26
		str += char
	}

	return reverString(str)

}

// 翻转字符串
func reverString(s string) string {
	str := []rune(s)
	l := 0
	r := len(s)

	for l < r {
		str[l], str[r-1] = str[r-1], str[l]
		l++
		r--
	}
	return string(str)
}

func code171(columnTitle string) int {
	s := reverString(columnTitle)
	str := []rune(s)

	n := len(columnTitle)
	num := 0

	for i := 0; i < n; i++ {

		tempNum := int(str[i]-'A'+1) * int(math.Pow(26, float64(i)))
		num += tempNum
	}
	return num

}

func code171Answer(columnTitle string) int {
	num := 0
	for i, multip := len(columnTitle)-1, 1; i >= 0; i-- {
		k := columnTitle[i] - 'A' + 1
		num += int(k) * multip
		multip *= 26
	}
	return num
}

// 同构字符串
func code205(s string, t string) bool {
	s2t := map[byte]byte{}
	t2s := map[byte]byte{}

	for i := range s {
		x, y := s[i], t[i]
		if (s2t[x] > 0 && s2t[x] != y) || (t2s[y] > 0 && t2s[y] != x) {
			return false
		}
		s2t[x] = y
		t2s[y] = x
	}

	return true
}

// 242. 有效的字母异位词  自己写的贼垃圾虽然通过了
func code242Bob(s string, t string) bool {
	smap := map[byte]int{}
	tmap := map[byte]int{}

	for i := range s {
		x := s[i]
		if smap[x] > 0 {
			smap[x] += 1
		} else {
			smap[x] = 1
		}

	}

	for i := range t {
		y := t[i]
		if tmap[y] > 0 {
			tmap[y] += 1
		} else {
			tmap[y] = 1
		}

	}

	for k, v := range smap {

		if v != tmap[k] {
			return false
		}
	}

	for k, v := range tmap {

		if v != smap[k] {
			return false
		}
	}

	return true

}

func isAnagram(s, t string) bool {
	s1, s2 := []byte(s), []byte(t)
	sort.Slice(s1, func(i, j int) bool { return s1[i] < s1[j] })
	sort.Slice(s2, func(i, j int) bool { return s2[i] < s2[j] })
	return string(s1) == string(s2)
}

func isAnagram2(s, t string) bool {
	var c1, c2 [26]int
	for _, ch := range s {
		c1[ch-'a']++
	}
	for _, ch := range t {
		c2[ch-'a']++
	}
	return c1 == c2
}

func code290(pattern string, s string) bool {
	strArr := strings.Split(s, " ")
	pMap := map[byte]string{}
	sMap := map[string]byte{}

	if len(pattern) != len(strArr) {
		return false
	}

	for i := range pattern {
		x, y := pattern[i], strArr[i]

		if len(pMap[x]) > 0 && pMap[x] != y || sMap[y] > 0 && sMap[y] != x {
			return false
		}

		pMap[x] = y
		sMap[y] = x

	}
	return true

}

//20230129看到这里

// code463 岛屿的周长
type pair struct {
	x int
	y int
}

var dir4 = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

//grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
func code463(grid [][]int) (ans int) {
	n, m := len(grid), len(grid[0])

	var dfs func(x, y int)
	dfs = func(x, y int) {
		if x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0 {
			ans++
			return
		}
		if grid[x][y] == 2 {
			return
		}
		grid[x][y] = 2
		for _, d := range dir4 {
			dfs(x+d.x, y+d.y)
		}
	}

	for i, row := range grid {
		for j, v := range row {
			if v == 1 {
				dfs(i, j)
			}
		}
	}
	return
}

// code344翻转字符串
func code344(s []byte) {
	for left, right := 0, len(s)-1; left < right; left++ {
		s[left], s[right] = s[right], s[left]
		right--
	}

}

func code345(s string) string {
	var hash [128]bool
	var char = [...]byte{'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}
	for _, c := range char {
		index := byte(c)
		hash[index] = true
	}

	str := []rune(s)

	for i, n := 0, len(s)-1; i < n; {
		left := byte(str[i])
		right := byte(str[n])
		if hash[left] && hash[right] {
			str[i], str[n] = str[n], str[i]
			i++
			n--
		} else {
			if !hash[left] {
				i++
			}
			if !hash[right] {
				n--
			}
		}
	}
	return string(str)
}

// 自己想的
func code385Bob(ransomNote string, magazine string) bool {

	ranMap := map[byte]int{}
	magMap := map[byte]int{}
	for _, value := range ransomNote {
		if ranMap[byte(value)] > 0 {
			ranMap[byte(value)]++
		} else {
			ranMap[byte(value)] = 1
		}
	}

	for _, value := range magazine {
		if (magMap[byte(value)]) > 0 {
			magMap[byte(value)]++

		} else {
			magMap[byte(value)]++
		}
	}

	for key, value := range ranMap {
		num := magMap[key]
		if num < value {
			return false
		}
	}
	return true
}

func code385(ransomNote, magazine string) bool {
	if len(magazine) < len(ransomNote) {
		return false
	}
	var ch [26]int

	for _, char := range magazine {
		ch[char-'a']++
	}

	for _, char := range ransomNote {

		ch[char-'a']--
		if ch[char-'a'] < 0 {
			return false
		}
	}
	return true
}

// 485. 最大连续 1 的个数
func code485(nums []int) int {
	var ans = 0
	var temp = 0
	for i := 0; i < len(nums); i++ {
		if nums[i] == 1 {
			temp++
		} else {
			temp = 0
		}
		if ans <= temp {
			ans = temp
		}
	}
	return ans

}

//20230220 看到这里

// 387. 字符串中的第一个唯一字符
func code387(s string) int {
	char := [26]int{}
	for _, value := range s {
		char[value-'a']++
	}
	for index, v := range s {
		if char[v-'a'] == 1 {
			return index
		}
	}
	return -1
}

// 389. 找不同
func code389(s, t string) byte {
	sMap := map[byte]int{}

	for _, char := range s {
		sMap[byte(char)] += 1
	}

	for _, char := range t {
		sMap[byte(char)] -= 1
		if sMap[byte(char)] < 0 {
			return byte(char)
		}

	}

	return 1

}

// 495 提莫的攻击
func code495(timeSeries []int, duration int) int {
	var last = -1 //上一次攻击结束的时间点
	var ans = 0   //总共的持续时间

	for _, s := range timeSeries {
		e := s + duration - 1
		//如果此次攻击重合
		if last >= s {
			ans += e - last
		} else {
			ans += duration
		}
		last = e
	}
	fmt.Println()

	return ans
}

//20230220看到这里

// 自己想的  496. 下一个更大元素 I
func code496(nums1 []int, nums2 []int) []int {

	// var nums2Map map[int]int
	nums2Map := map[int]int{}

	for i := 0; i < len(nums2); i++ {
		nums2Map[nums2[i]] = i
	}

	arr := make([]int, len(nums1))

	for index, value := range nums1 {
		arr[index] = -1
		k := nums2Map[value]
		if k >= 0 {
			for ; k < len(nums2); k++ {
				if nums2[k] > value {

					arr[index] = nums2[k]
					break
				}
			}
		}
	}

	return arr
}

// func findWords(words []string) []string {
// 	fistrLine := []byte{'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', 'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P'}
// 	secondLine := []byte{'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'A', 'S', 'D', 'F', 'G', 'H', 'J', 'K', 'L'}
// 	thirdLine := []byte{'z', 'x', 'c', 'v', 'b', 'n', 'm', 'Z', 'X', 'C', 'V', 'B', 'N', 'M'}

// 	returnArr := words[:]

// 	for index, word := range words {

// 		tempLine := make([]byte, 0)
// 		for _, find := range fistrLine {
// 			if word[0] == find {
// 				tempLine = fistrLine
// 			}
// 		}

// 		for _, find := range secondLine {
// 			if word[0] == find {
// 				tempLine = secondLine
// 			}
// 		}

// 		for _, find := range thirdLine {
// 			if word[0] == find {
// 				tempLine = thirdLine
// 			}
// 		}

// 		for _, charInner := range word {
// 			for _, b := range tempLine {
// 				if byte(charInner) != b {
// 					returnArr = append(returnArr[:index], returnArr[index+1:]...)
// 				}

// 			}

// 		}
// 	}

// 	return returnArr

// }

// 500. 键盘行
// 没看太懂
func findWords(words []string) (ans []string) {
	var arr [5]string
	arr = [5]string{"1,2,3,4,5"}
	fmt.Println(arr)
	const rowIdx = "12210111011122000010020202"
next:
	for _, word := range words {
		test := unicode.ToLower(rune(word[0])) - 'a'
		fmt.Println(test)
		idx := rowIdx[unicode.ToLower(rune(word[0]))-'a']
		fmt.Println(rowIdx[7])
		for _, ch := range word[1:] {
			if rowIdx[unicode.ToLower(ch)-'a'] != idx {
				continue next
			}
		}
		ans = append(ans, word)
	}
	return
}

//0221看到这里

// 冒泡排序 (从大到小排)
func BubbleSort2(arr []int) {
	len := len(arr)
	changed := false //没有需要交换的则说明数组已经排好序了
	for i := 0; i < len-1; i++ {
		for j := 0; j < len-1-i; j++ {
			if arr[j] < arr[j+1] {
				changed = true
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
		if !changed { //已经排好序不用循环了
			break
		}
	}

}

// 相对名字 自己写的
func code506Bob(score []int) []string {
	sortScore := make([]int, len(score))

	for k, v := range score {
		sortScore[k] = v
	}

	//1.对score排序，第一名放到最前面  sortScort
	//BubbleSort()
	//BubbleSort(sortScore)

	//两个for循环确定
	len := len(score)
	result := make([]string, len)

	for k, v := range score {
		for i := 0; i <= len-1; i++ {
			if v == sortScore[i] {
				sort := strconv.Itoa(i + 1)
				switch sort {
				case "1":
					sort = "Gold Medal"
				case "2":
					sort = "Silver Medal"
				case "3":
					sort = "Bronze Medal"
				}

				result[k] = sort
			}
		}
	}
	return result

}

var sortSlice = []string{"Gold Medal", "Silver Medal", "Bronze Medal"}

func findRelativeRanks(score []int) []string {
	type pair struct {
		score int
		sort  int
	}
	len := len(score)
	arr := make([]pair, len)

	for k, v := range score {
		arr[k] = pair{v, k}
	}

	sort.Slice(arr, func(i, j int) bool { return arr[i].score > arr[j].score })

	ans := make([]string, len)

	for k, v := range arr {
		if k < 3 {
			ans[v.sort] = sortSlice[k]
		} else {
			ans[v.sort] = strconv.Itoa(k)
		}
	}

	return ans
}

//code682 棒球比赛
func calPoints(operations []string) int {
	//rsArr := [...]int{}
	var rsArr []int

	for _, v := range operations {
		length := len(rsArr)
		switch v {
		case "+":
			nowValue := rsArr[length-1] + rsArr[length-2]
			nowValue = int(nowValue)
			rsArr = append(rsArr, nowValue)
			break
		case "D":
			nowValue := rsArr[length-1] * 2
			nowValue = int(nowValue)
			rsArr = append(rsArr, nowValue)
			break
		case "C":
			rsArr = rsArr[0 : length-1]
			break
		default:
			nowValue, _ := strconv.Atoi(v)
			rsArr = append(rsArr, nowValue)
		}
	}

	var result int
	for _, v := range rsArr {
		result += v
	}
	return result

}

//code 674. 最长连续递增序列
func findLengthOfLCIS(nums []int) int {
	if len(nums) == 1 {
		return 1
	}
	max, temMax := 1, 1
	for i := 1; i < len(nums); i++ {
		if nums[i] > nums[i-1] {
			temMax += 1
		} else {
			temMax = 1
		}

		if temMax >= max {
			max = temMax
		}

	}
	return max
}

//605. 种花问题
func canPlaceFlowers(flowerbed []int, n int) bool {
	// 如果花种完了，或者花床检查完了，都停止遍历
	for i, length := 0, len(flowerbed); i < length && n > 0; {
		if flowerbed[i] == 1 {
			//即如果，当前i位置已经种植了话，那么下一个可以种花的位置是 i+2
			i += 2
		} else if i == length-1 || flowerbed[i+1] == 0 {
			//这里很关键
			//如果是最后一个位置了，那么肯定能够种植（i==flowerbed.length-1)
			//如果不是，则还需要确保 可种花的位置(i+2)紧邻其后的(i+2+1)的位置没有种植（flowerbed[i+1]==0)
			//只有这样才可以种植
			n--
			//同时找出下一个可以种植的位置
			i += 2
		} else {
			//这种情况是flowerbed[i+2+1]=1，所以下次循环就从这里重新开始判断其后可种植的位置
			i += 3
		}
	}
	return n <= 0
}

func maximumProduct(nums []int) int {
	sort.Ints(nums)
	n := len(nums)
	return max(nums[0]*nums[1]*nums[n-1], nums[n-3]*nums[n-2]*nums[n-1])
}
